// purpose: bitmap management for lsv, bitmap cow snapshot implemention.

// file created by zsy on 2017.03.06

#include <dirent.h>
#include <stack.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>

#include "list.h"
#include "lsv_volume.h"
#include "lsv_bitmap.h"
#include "lsv_bitmap_internal.h"
#include "lsv_help.h"
#include "lsv_volume_proto.h"

#include "lsv_wbuffer.h"
#include "table_proto.h"
#include "volume_proto.h"

extern uint32_t lsv_feature;

int lsv_bitmap_link_appand_child(struct lsv_bitmap_context *parent, struct lsv_bitmap_context *node)
{
        struct lsv_bitmap_context *p = parent->first_child;

        node->parent = parent;

        if (!p) {
                parent->first_child = node;
                parent->bitmap_header->first_child_chunk_id = node->bitmap_header->header_chunk_ids[0];

                return bitmap_header_save(parent, SAVE_HEADER_LEVEL_META);
        }

        if (!p->next) {
                p->next = node;
                p->bitmap_header->next_chunk_id = node->bitmap_header->header_chunk_ids[0];

                return bitmap_header_save(p, SAVE_HEADER_LEVEL_META);
        } else {
                while (p->next) {
                        p = p->next;
                }

                p->next = node;
                p->bitmap_header->next_chunk_id = node->bitmap_header->header_chunk_ids[0];

                return bitmap_header_save(p, SAVE_HEADER_LEVEL_META);
        }
}

int lsv_bitmap_link_drop_node(struct lsv_bitmap_context *node)
{
        int ret = -1;

        struct lsv_bitmap_context *parent = node->parent;
        struct lsv_bitmap_context *first_child = node->first_child;
        struct lsv_bitmap_context *root = lsv_bitmap_get_root(node);

        LSV_DBUG("enter\r\n");

        if (parent->first_child == node) {
                parent->first_child = node->next;
                parent->bitmap_header->first_child_chunk_id = node->next ? node->next->bitmap_header->header_chunk_ids[0] : 0;

                ret = bitmap_header_save(parent, SAVE_HEADER_LEVEL_META);
        } else {
                struct lsv_bitmap_context *p = parent->first_child->next;
                struct lsv_bitmap_context *prev = parent->first_child;
                while (p) {
                        if (p == node) {
                                prev->next = node->next;
                                prev->bitmap_header->next_chunk_id = node->next ? node->next->bitmap_header->header_chunk_ids[0] : 0;

                                ret = bitmap_header_save(prev, SAVE_HEADER_LEVEL_META);

                                break;
                        }

                        prev = p;
                        p = p->next;
                }
        }

        if (ret)
                return ret;

        while (first_child) {
                first_child->parent = parent;

                if (first_child == node->first_child)// do the first one.
                {
                        ret = lsv_bitmap_link_appand_child(parent, first_child);
                        if (ret) {
                                DERROR("lsv_bitmap_link_appand_child failed, rc = %d\r\n", ret);
                                break;
                        }
                }

                first_child = first_child->next;
        }

        if (!root->first_child && !root->next && root->active) {
                root->active = NULL;
                root->bitmap_header->active_chunk_id = 0;

                ret = bitmap_header_save(root, SAVE_HEADER_LEVEL_META);
        }

        node->parent = NULL;

        return ret;
}

void lsv_bitmap_link_change_parent(struct lsv_bitmap_context *node, struct lsv_bitmap_context *new_parent)
{
        lsv_bitmap_link_drop_node(node);
        lsv_bitmap_link_appand_child(new_parent, node);
}

struct lsv_bitmap_context *lsv_bitmap_get_root(struct lsv_bitmap_context *node)
{
        struct lsv_bitmap_context *p = node;

        while (p->parent)
                p = p->parent;

        return p;
}

struct lsv_bitmap_context *lsv_bitmap_get_parent_volume(struct lsv_bitmap_context *node)
{
        struct lsv_bitmap_context *p = node->parent;

        while (p) {
                if (p->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_VOLUME)
                        return p;

                p = p->parent;
        }

        return NULL;
}

struct lsv_bitmap_context *lsv_bitmap_get_current_volume(struct lsv_bitmap_context *node)
{
        struct lsv_bitmap_context *p = node;

        while (p) {
                if (p->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_VOLUME)
                        return p;

                p = p->parent;
        }

        // TODO core is_loading == 1
        assert(FALSE);

        return NULL;
}

struct lsv_bitmap_context *lsv_bitmap_get_active_node(struct lsv_bitmap_context *node)
{
        /*struct lsv_bitmap_context * active = NULL;
          struct lsv_bitmap_context *p = node->next;

          if(node->is_active)
          return node;

          while(p)
          {
          active = lsv_bitmap_get_active_node(p);
          if(active)
          return active;

          p = p->next;
          }

          if(node->first_child)
          {
          active = lsv_bitmap_get_active_node(node->first_child);

          if(active)
          return active;
          }

          return NULL;*/

        return node->active;
}

struct lsv_bitmap_context *lsv_bitmap_get_by_name(struct lsv_bitmap_context *node, const char *name)
{
        // struct lsv_bitmap_context *p = NULL;

        stack_context_t stack;

        stack_init(&stack);

        stack_push(&stack, node);

        while (!stack_empty(&stack)) {
                struct lsv_bitmap_context *node = stack_pop(&stack);

                if (strcmp(name, node->bitmap_header->name) == 0)
                        return node;

                if (node->next)
                        stack_push(&stack, node->next);

                if (node->first_child)
                        stack_push(&stack, node->first_child);
        }
        /*if(strcmp(name, node->bitmap_header->name) == 0)
                return node;

        if(node->first_child)
                p = lsv_bitmap_get_by_name(node->first_child, name);

        if(p)
                return p;

        if(node->next)
                p = lsv_bitmap_get_by_name(node->next, name);
*/
        return NULL;
}

int lsv_bitmap_set_active_node(struct lsv_bitmap_context *vol_node, struct lsv_bitmap_context *current)
{
        vol_node->active = current;
        vol_node->bitmap_header->active_chunk_id = current->bitmap_header->header_chunk_ids[0];

        return bitmap_header_save(vol_node, SAVE_HEADER_LEVEL_META);
}

int lsv_bitmap_has_snapshot(void *volume_context)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        if (root->first_child)
                return 1;
        else
                return 0;
}
struct lsv_bitmap_context *lsv_bitmap_volume_to_node(void *volume_context)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_active_node(root);

        if (node)
                return node;
        else
                return root;
}

struct lsv_bitmap_context *lsv_bitmap_get_root_node(void *volume_context)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;

        while (root->parent)
                root = root->parent;

        return root;
}

uint8_t lsv_is_bitmap(void *volume_context)
{
        (void)volume_context;
        return 0;
}

int lsv_bitmap_copy_trunk(void *volume_context, uint32_t src_chunk_id, uint32_t dest_chunk_id)
{
        void *buf = xmalloc(CHUNK_SIZE);

        // int ret = lsv_bitmap_read_chunk(volume_context, 0, src_chunk_id, 0, CHUNK_SIZE, buf);
        // ret = lsv_bitmap_write_chunk(volume_context, src_chunk_id, 0, CHUNK_SIZE, buf);

        (void)volume_context;
        (void)src_chunk_id;
        (void)dest_chunk_id;
        xfree(buf);

        return 0;
}

int lsv_bitmap_copy_trunk_page(void *volume_context, uint32_t src_chunk_id, uint32_t dest_chunk_id, uint32_t page_idx, uint32_t page_count)
{
        void *buf = xmalloc(CHUNK_SIZE);

        int ret = lsv_bitmap_read_chunk(volume_context, 0, src_chunk_id, page_idx * LSV_PAGE_SIZE, page_count * LSV_PAGE_SIZE, buf);
        ret |= lsv_bitmap_write_chunk(volume_context, dest_chunk_id, page_idx * LSV_PAGE_SIZE, page_count * LSV_PAGE_SIZE, buf);

        xfree(buf);

        return ret;
}

int lsv_bitmap_copy_and_update(struct lsv_bitmap_context *bitmap_context, uint32_t chunk_index)
{
        int ret;
        // struct lsv_bitmap_context *parent = bitmap_context->parent;
        // uint32_t chunk_id = parent->bitmap_header->header_chunk_ids[chunk_index];
        uint32_t new_chunk_id;

        ret = lsv_bitmap_alloc_chunk(bitmap_context, &new_chunk_id, 0);
        if (ret) {
                // fatal error.
                return ret;
        }

        // int ret = 0;//lsv_bitmap_copy_trunk(chunk_id, new_chunk_id);
        if (ret) {
                // fatal error.
                return ret;
        }

        bitmap_context->bitmap_header->header_chunk_ids[chunk_index] = new_chunk_id;
        // save it.

        return 0;
}

int lsv_bimap_load_snapshot(void *volume_context, uint32_t first_chunk_id)
{
        int ret;

        ret = bitmap_header_load(volume_context, first_chunk_id);
        if (ret)
                return ret;

        return -1;
}

int lsv_bitmap_create_snapshot_internal(void *volume_context, struct lsv_bitmap_context *parent_node, const char *snap_name, uint8_t type,
                                        struct lsv_bitmap_context **new_node)
{
        int ret = -1;
        struct lsv_bitmap_context *root;
        struct lsv_bitmap_context *active;
        uint64_t node_id = 0;

        if (parent_node) {
                root = lsv_bitmap_get_root(parent_node);

                // active = root->active;
        } else {
                root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
                parent_node = active = root->active;
                if (!parent_node)// no snapshot.
                        parent_node = root;
        }

        // create new snap on "lich_system_curr", just change name...
        if (parent_node->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE) {
                strcpy(parent_node->bitmap_header->name, snap_name);
                parent_node->bitmap_header->type_and_flag &= ~LSV_BITMAP_SNAP_TYPE_HERE;

                ret = bitmap_header_save(parent_node, SAVE_HEADER_LEVEL_META);
                if (ret) {
                        DERROR("creating snapshot failed %d in header saving.\r\n", ret);

                        return ret;
                }

                snap_name = "lich_system_curr";
                type = LSV_BITMAP_SNAP_TYPE_HERE;
                node_id = parent_node->bitmap_header->node_id + 1;
        } else if (type == LSV_BITMAP_SNAP_TYPE_HERE)// first snapshot hear node.
                node_id = parent_node->bitmap_header->node_id + 1;
        else
                node_id = lsv_bitmap_snap_get_max_id(volume_context);// 0 + 1;
        // do create the snapshot.
        struct lsv_bitmap_context *node_new;

        DERROR("Creating node...\r\n");
        ret = lsv_bitmap_create_node(volume_context, &node_new, LSV_BITMAP_FALSE, type);
        if (ret) {
                DERROR("creating snapshot failed %d in creating node.\r\n", ret);

                return ret;
        }

        node_new->bitmap_header->node_id = node_id;
        strncpy(node_new->bitmap_header->name, snap_name, sizeof(node_new->bitmap_header->name));

        // for(int i=0;i<sizeof(parent_node->bitmap_header->header_chunk_ids) / sizeof(uint32_t); i++)
        //{
        // if(!parent_node->bitmap_header->header_chunk_ids[i])
        //     continue;

        DERROR("Coying header...\r\n");

        for (int j = 0; j < parent_node->bitmap_header->chunk_map_count; j++) {
                node_new->bitmap_header->chunk_map[j].chunk_id = parent_node->bitmap_header->chunk_map[j].chunk_id;
                node_new->bitmap_header->chunk_map[j].vvol_id = parent_node->bitmap_header->chunk_map[j].vvol_id;
                node_new->bitmap_header->chunk_map[j].is_ref = 1;

                LSV_DBUG("chunk_map %u, chunk_id %u\r\n", j, node_new->bitmap_header->chunk_map[j].chunk_id);
        }

        int idx = 0;
        for (idx = 0; idx <= parent_node->bitmap_header->vvol_id; idx++)// copy from parent.
        {
                node_new->bitmap_header->vvol_map[idx] = parent_node->bitmap_header->vvol_map[idx];
        }

        // for snapshot not increase vvolid;
        node_new->bitmap_header->vvol_id = parent_node->bitmap_header->vvol_id;

        DERROR("Saving header...\r\n");

        // ret = lsv_bitmap_copy_trunk(volume_context,
        //                            parent_node->bitmap_header->header_chunk_ids[i],
        //                            node_new->bitmap_header->header_chunk_ids[i]);

        ret = bitmap_header_save(node_new, SAVE_HEADER_LEVEL_ALL);

        if (ret) {
                // delete node.

                for (int j = 0; j < sizeof(node_new->bitmap_header->header_chunk_ids) / sizeof(uint32_t); j++)
                        lsv_volume_chunk_free(volume_context, LSV_BITMAP_STORAGE_TYPE, node_new->bitmap_header->header_chunk_ids[j]);

                lsv_bitmap_free_single_node(node_new);

                DERROR("creating snapshot failed %d in header saving.\r\n", ret);

                return ret;
        }

        // }

        DERROR("Set active...\r\n");

        ret = lsv_bitmap_set_active_node(root, node_new);
        if (!ret) {
                ret = lsv_bitmap_link_appand_child(parent_node, node_new);

                if (new_node)
                        *new_node = node_new;
        }

        if (ret)
                DERROR("creating snapshot failed %d in setting active.\r\n", ret);

        return ret;
}

int lsv_bitmap_create_snapshot(void *volume_context, struct lsv_bitmap_context *parent_node, const char *snap_name, struct lsv_bitmap_context **new_node)
{
        int ret;

        lsv_bitmap_wlock(volume_context);

        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_by_name(root, snap_name);

        if (node) {
                lsv_bitmap_unlock(volume_context);

                return EEXIST;
        }

        LSV_DBUG("creating snapshot %s ...\r\n", snap_name);

        lsv_bitmap_release_cache(volume_context);

        if (!root->first_child) {
                struct lsv_bitmap_context *ptmp;

                ret = lsv_bitmap_create_snapshot_internal(volume_context, parent_node, snap_name, LSV_BITMAP_SNAP_TYPE_PERSISTENT, &ptmp);
                if (ret) {
                        return ret;
                }
                ret |= lsv_bitmap_create_snapshot_internal(volume_context, ptmp, "lich_system_curr", LSV_BITMAP_SNAP_TYPE_HERE, new_node);
        } else
                ret = lsv_bitmap_create_snapshot_internal(volume_context, parent_node, snap_name, LSV_BITMAP_SNAP_TYPE_PERSISTENT, new_node);

        LSV_DBUG("creating snapshot %s finished, status=%d ...\r\n", snap_name, ret);

        lsv_bitmap_unlock(volume_context);

        return ret;
}

int lsv_bitmap_free_data_chunks(void *volume_context, uint32_t vvol_id, struct lsv_bitmap_context *node, uint32_t chunk_id)
{
        // lsv_volume_proto_t *lsv_info = (lsv_volume_proto_t *)volume_context;
        // struct lsv_bitmap_context * root = (struct lsv_bitmap_context * )lsv_info->bitmap_context;
        int ret;
        void *bitmap_buf;

        bitmap_buf = xmalloc(LSV_CHUNK_SIZE);
        ret = lsv_read_bitmap_node(node, vvol_id, chunk_id, 0, LSV_CHUNK_SIZE, bitmap_buf);
        if (ret) {
                DERROR("lsv_read_bitmap_node failed, err:%d\r\n", ret);
                return ret;
        }

        struct lsv_bitmap_unit *punit = (struct lsv_bitmap_unit *)bitmap_buf;

        for (int i = 0; i < CHUNK_SIZE / sizeof(struct lsv_bitmap_unit); i++) {
                if (punit->chunk_id && !punit->ref) {
                        lsv_volume_chunk_free(volume_context, LSV_LOG_LOG_STORAGE_TYPE, punit->chunk_id);
                }

                punit++;
        }

        // lsv_bitmap_cache_page_unlock(cache_ref, 0, CHUNK_SIZE / PAGE_SIZE);
        // lsv_bitmap_cache_unlock(cache_ref);

        return 0;
}

int lsv_bitmap_merge_pages(void *volume_context, struct row2_bitmap_unit *unit, struct row2_bitmap_unit *unit_to)
{
        lsv_volume_proto_t *lsv_info = (lsv_volume_proto_t *)volume_context;
        struct lsv_bitmap_context *root = (struct lsv_bitmap_context *)lsv_info->bitmap_context;
        // int copy_all = 0;

        if (!unit->owner)// nothing to copy.
                return 0;

        // if(!unit_to->owner)
        //        copy_all = 1;

        for (int i = 0; i < CHUNK_SIZE / LSV_PAGE_SIZE; i++) {
                if (unit_to->page_bits[i].chunk_id == unit->chunk_id && root->bitmap_header->vvol_id == unit_to->page_bits[i].vvol_id) {
                        // data merge.
                        unit_to->page_bits[i].chunk_id = unit_to->chunk_id;
                        lsv_bitmap_copy_trunk_page(volume_context, unit->chunk_id, unit_to->chunk_id, i, 1);
                }
        }

        return 0;
}

int lsv_bitmap_merge_data_chunks(uint32_t vvol_id, struct lsv_bitmap_context *node, uint32_t pos, struct lsv_bitmap_context *to_node)
{
        lsv_bitmap_cache_unit_t *cache_ref, *cache_ref_to;
        uint32_t chunk_id, chunk_id_to;
        uint8_t *cache_buf, *cache_buf_to;

        chunk_id = node->bitmap_header->chunk_map[pos].chunk_id;
        chunk_id_to = to_node->bitmap_header->chunk_map[pos].chunk_id;

        cache_buf = lsv_bitmap_cache_get(node, vvol_id, chunk_id, 0, CHUNK_SIZE, 0, &cache_ref);
        cache_buf_to = lsv_bitmap_cache_get(node, vvol_id, chunk_id_to, 0, CHUNK_SIZE, 0, &cache_ref_to);
        assert(cache_buf);

        struct row2_bitmap_unit *unit = (struct row2_bitmap_unit *)cache_buf;
        struct row2_bitmap_unit *unit_to = (struct row2_bitmap_unit *)cache_buf_to;

        for (int i = 0; i < CHUNK_SIZE / sizeof(struct row2_bitmap_unit); i++) {
                if (unit->chunk_id && !unit_to->chunk_id) {
                        lsv_bitmap_merge_pages(node->volume_context, unit, unit_to);
                }

                unit++;
                unit_to++;
        }

        // lsv_bitmap_cache_page_unlock(cache_ref, 0, CHUNK_SIZE / PAGE_SIZE);
        // lsv_bitmap_cache_page_unlock(cache_buf_to, 0, CHUNK_SIZE / PAGE_SIZE);

        lsv_bitmap_cache_unlock(cache_ref);
        lsv_bitmap_cache_unlock(cache_ref_to);
        return 0;
}

int lsv_bitmap_revert_snapshot_internal(void *volume_context, struct lsv_bitmap_context *new_parent)
{
        lsv_volume_proto_t *lsv_info = (lsv_volume_proto_t *)volume_context;
        struct lsv_bitmap_context *root = (struct lsv_bitmap_context *)lsv_info->bitmap_context;

        struct lsv_bitmap_context *active = lsv_bitmap_get_active_node(BITMAP_CONTEXT(volume_context));
        if (!active)
                return -1;// no snapshot.

        struct lsv_bitmap_context *parent = new_parent ? (new_parent == active ? active->parent : new_parent) : active->parent;
        if (!parent)
                return -1;// no snapshot.

        // no zero data goto.
        if (active->parent != parent && !(active->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE)) {
                struct lsv_bitmap_context *tmp;
                return lsv_bitmap_create_snapshot_internal(volume_context, new_parent, "lich_system_curr", LSV_BITMAP_SNAP_TYPE_HERE, &tmp);
        }

        // for(int i=0;i<sizeof(parent->bitmap_header->header_chunk_ids) / sizeof(uint32_t); i++)
        //{
        //    if(!parent->bitmap_header->header_chunk_ids[i])
        //        continue;

        for (int j = 0; j < parent->bitmap_header->chunk_map_count; j++) {
                // free chunk.
                if (!active->bitmap_header->chunk_map[j].is_ref) {
                        // todo.
                        // lsv_volume_chunk_free(volume_context, LSV_BITMAP_STORAGE_TYPE,active->bitmap_header->chunk_map[j].chunk_id);
                        if (lsv_info->volume_format == VOLUME_FORMAT_ROW2 || lsv_info->volume_format == VOLUME_FORMAT_ROW3)
                                lsv_bitmap_free_data_chunks(volume_context, root->bitmap_header->vvol_id, active, active->bitmap_header->chunk_map[j].chunk_id);
                }

                active->bitmap_header->chunk_map[j].chunk_id = parent->bitmap_header->chunk_map[j].chunk_id;
                active->bitmap_header->chunk_map[j].is_ref = 1;
        }
        //}

        // zero data and goto.
        if (active->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE) {
                lsv_bitmap_link_change_parent(active, parent);

                return bitmap_header_save(active, SAVE_HEADER_LEVEL_ALL);
        }

        if (!root->next && root->first_child && !root->first_child->first_child && !root->first_child->next &&
            (root->first_child->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE)) {
                lsv_bitmap_delete_snapshot_internal(root->first_child);
        }

        // just revert.
        return bitmap_header_save(active, SAVE_HEADER_LEVEL_ALL);
}

int lsv_bitmap_revert_snapshot(void *volume_context, const char *snap_name)
{
        int ret;

        lsv_bitmap_wlock(volume_context);

        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_by_name(root, snap_name);

        if (!node)// not found.
        {
                lsv_bitmap_unlock(volume_context);

                return -1;
        }

        LSV_DBUG("Reverting snapshot %s ...\r\n", snap_name);
        ret = lsv_bitmap_revert_snapshot_internal(volume_context, node);
        LSV_DBUG("Reverted snapshot %s, %d ...\r\n", snap_name, ret);

        lsv_bitmap_unlock(volume_context);

        return ret;
}

int lsv_bitmap_mark_node_deleted(struct lsv_bitmap_context *node, int delete)
{
        LSV_DBUG("mark node deleted: %p\r\n", node);

        if (delete)
                node->bitmap_header->type_and_flag |= LSV_BITMAP_SNAP_TYPE_DELETED;
        else
                node->bitmap_header->type_and_flag &= ~LSV_BITMAP_SNAP_TYPE_DELETED;

        return bitmap_header_save(node, SAVE_HEADER_LEVEL_META);
}

int lsv_bitmap_delete_snapshot_internal(struct lsv_bitmap_context *bitmap_context)
{
        int ret = 0;
        struct lsv_bitmap_context *parent = bitmap_context->parent;

        if (!parent)
                return -1;// no snapshot.

        for (int i = 0; i < sizeof(parent->bitmap_header->header_chunk_ids) / sizeof(uint32_t); i++) {
                int bFound = 0;

                if (!parent->bitmap_header->header_chunk_ids[i])
                        break;

                if (bitmap_context->bitmap_header->header_chunk_ids[i] != parent->bitmap_header->header_chunk_ids[i]) {
                        struct lsv_bitmap_context *p = bitmap_context->first_child;

                        while (p) {
                                if (p->bitmap_header->header_chunk_ids[i] == bitmap_context->bitmap_header->header_chunk_ids[i]) {
                                        bFound = 1;
                                        break;
                                }

                                p = p->next;
                        }
                } else
                        bFound = 1;

                if (!bFound) {
                        ret =
                            lsv_volume_chunk_free(bitmap_context->volume_context, LSV_BITMAP_STORAGE_TYPE, bitmap_context->bitmap_header->header_chunk_ids[i]);
                }

                if (ret) {
                        // failed in free trunk.

                        return ret;
                }
        }

        LSV_DBUG("Snapshot deleted, processing links...\r\n");
        // todo, link processing.
        lsv_bitmap_link_drop_node(bitmap_context);

        LSV_DBUG("Current node %p, first child %p, parent first child %p, \r\n", bitmap_context, bitmap_context->first_child, parent->first_child);

        lsv_bitmap_free_single_node(bitmap_context);

        return 0;
}

static inline int lsv_bitmap_snap_is_leaf(struct lsv_bitmap_context *node)
{
        if (node->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE)
                return 0;
        else if (!node->first_child)
                return 1;
        else if ((node->first_child->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE) && !node->first_child->next && !node->first_child->first_child)
                return 1;
        else
                return 0;
}

int lsv_bitmap_delete_snapshot(void *volume_context, const char *snap_name)
{
        lsv_bitmap_wlock(volume_context);

        lsv_volume_proto_t *lsv_info = (lsv_volume_proto_t *)volume_context;

        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_by_name(root, snap_name);
        struct lsv_bitmap_context *parent = node ? node->parent : NULL;

        if (!node)// not found.
        {
                lsv_bitmap_unlock(volume_context);

                return ENOENT;
        }

        if (node->bitmap_header->type_and_flag & LSV_BITMAP_FLAG_PROTECTED) {
                LSV_DBUG("Deleting snapshot failed, node protected %s ...\r\n", snap_name);

                lsv_bitmap_unlock(volume_context);

                return EPERM;
        }

        if (lsv_info->volume_format == VOLUME_FORMAT_ROW2 && !lsv_bitmap_snap_is_leaf(node)) {
                lsv_bitmap_unlock(volume_context);

                return lsv_bitmap_mark_node_deleted(node, 1);
        }

        LSV_DBUG("Deleting snapshot %s ...\r\n", snap_name);
        int ret = lsv_bitmap_delete_snapshot_internal(node);
        if (!ret) {
                if (!root->next && root->first_child && !root->first_child->first_child && !root->first_child->next &&
                    (root->first_child->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_HERE)) {
                        lsv_bitmap_delete_snapshot_internal(root->first_child);
                } else if (node->first_child) {
                        ret = lsv_bitmap_revert_snapshot_internal(lsv_info, parent);
                        if (ret)
                                goto end;
                }

                if (lsv_info->volume_format == VOLUME_FORMAT_ROW2) {
                        while (parent && lsv_bitmap_snap_is_leaf(parent) && (parent->bitmap_header->type_and_flag & LSV_BITMAP_SNAP_TYPE_DELETED)) {
                                struct lsv_bitmap_context *_parent = parent->parent;

                                if (parent->first_child)// must be here.
                                {
                                        ret = lsv_bitmap_revert_snapshot_internal(lsv_info, parent);
                                }

                                ret = lsv_bitmap_delete_snapshot_internal(parent);
                                if (ret)
                                        goto end;

                                parent = _parent;
                        }

                        // lsv_bitmap_unlock(volume_context);
                        // return lsv_bitmap_mark_node_deleted(node, 1);
                }
        }

        LSV_DBUG("Deleted snapshot %s, %d ...\r\n", snap_name, ret);

end:
        lsv_bitmap_unlock(volume_context);

        return ret;
}

int lsv_bitmap_protect_node(struct lsv_bitmap_context *node, int protect)
{
        if (protect)
                node->bitmap_header->type_and_flag |= LSV_BITMAP_FLAG_PROTECTED;
        else
                node->bitmap_header->type_and_flag &= ~LSV_BITMAP_FLAG_PROTECTED;

        return bitmap_header_save(node, SAVE_HEADER_LEVEL_META);
}

int lsv_bitmap_protect_snapshot(void *volume_context, const char *snap, int protect)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_by_name(root, snap);
        if (!node)
                return -1;

        return lsv_bitmap_protect_node(node, protect);
}

int lsv_bitmap_read_snapshot_meta(void *volume_context, const char *snap, uint64_t off, uint32_t len, void *buffer)
{
        LSV_DBUG("lsv_bitmap_read_snapshot_meta\r\n");

        int ret;
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        struct lsv_bitmap_context *node = lsv_bitmap_get_by_name(root, snap);
        if (!node) {
                LSV_DBUG("lsv_bitmap_read_snapshot_meta no node\r\n");
                return -1;
        }

        ret = bitmap_header_read(node, off, len, buffer);

        LSV_DBUG("lsv_bitmap_read_snapshot_meta end %d\r\n", ret);

        return ret;
}

int lsv_bitmap_print_tree_to_dir(struct lsv_bitmap_context *node, int fd, off_t *off)
{
        int ret;
        struct dirent de;

        if (!node->parent)
                goto out;

        memset(&de, 0x0, sizeof(de));
        sprintf(de.d_name, "%s %ld %s %ld", node->bitmap_header->name, node->bitmap_header->node_id,
                (strlen(node->parent->bitmap_header->name) == 0 ? LICH_SYSTEM_ATTR_ROOT : node->parent->bitmap_header->name),
                (strlen(node->parent->bitmap_header->name) == 0 ? -1 : node->parent->bitmap_header->node_id));
        de.d_off = *off;
        de.d_reclen = sizeof(de) + +MAX_NAME_LEN;

        DWARN("snapshot name:%s\n", de.d_name);

        ret = _pwrite(fd, &de, de.d_reclen, *off);
        if (ret < 0) {
                ret = -ret;
                GOTO(err_ret, ret);
        }

        *off += de.d_reclen;

out:
        return 0;
err_ret:
        return ret;
}

void lsv_bitmap_list_snap_internal(struct lsv_bitmap_context *root_node, int fd, off_t *off)
{
        stack_context_t stack;

        stack_init(&stack);

        stack_push_arg(&stack, root_node, (void *)0);

        while (!stack_empty(&stack)) {
                void *arg;
                struct lsv_bitmap_context *node = stack_pop_arg(&stack, &arg);

                //*off = (off_t)arg;
                lsv_bitmap_print_tree_to_dir(node, fd, off);

                if (node->next) {
                        stack_push_arg(&stack, node->next, arg);

                        // node = node->next;
                }

                if (node->first_child) {
                        stack_push_arg(&stack, node->first_child, (void *)((uint64_t)arg + 1));
                }
        }
        /*lsv_bitmap_print_tree_to_dir(node,col);

        if(node->first_child) {
                lsv_bitmap_list_snap_internal(node->first_child, col + 1);
        }

        if(node->next) {
                lsv_bitmap_list_snap_internal(node->next, col);

        }*/
}

static int lsv_bitmap_list_snap_end(int fd, uint64_t offset)
{
        int ret;
        struct dirent de;

        memset(&de, 0x0, sizeof(de));
        de.d_name[0] = '\0';
        de.d_reclen = (sizeof(de) + MAX_NAME_LEN);
        de.d_off = offset;

        ret = _pwrite(fd, &de, de.d_reclen, offset);
        if (ret < 0) {
                ret = -ret;
                GOTO(err_ret, ret);
        }

        return 0;
err_ret:
        return ret;
}

int lsv_bitmap_list_snap(void *volume_context, int fd)
{
        off_t offset = 0;
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;

        DWARN("========snapshot list begin========\n");
        lsv_bitmap_list_snap_internal(root, fd, &offset);
        lsv_bitmap_list_snap_end(fd, offset);
        DWARN("========snapshot list end========\n");

        return 0;
}

uint32_t lsv_bitmap_snap_get_max_id(void *volume_context)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;

        return (root->active ? root->active : root)->bitmap_header->node_id;
}

// for gc
int lsv_bitmap_lba_check_node(struct lsv_bitmap_context *bitmap_context, uint64_t lba, uint32_t chunk_id, uint32_t chunk_page_off, uint32_t snap_id)
{
        stack_context_t stack;

        stack_init(&stack);

        stack_push(&stack, bitmap_context);

        LSV_DBUG("check lba %lld chunk %d page %d snap %d\r\n", (LLU)lba, chunk_id, chunk_page_off, snap_id);

        // first time check same id.
        while (!stack_empty(&stack)) {
                struct lsv_bitmap_context *node = stack_pop(&stack);
                struct lsv_bitmap_unit bitmap;

                if (node->bitmap_header->node_id == snap_id) {
                        int ret = lsv_bitmap_paged_read_node(node, lba, &bitmap);
                        if (ret)
                                return ret;

                        if (bitmap.chunk_id == chunk_id && bitmap.chunk_page_off == chunk_page_off)// data used.
                        {
                                LSV_DBUG("lba check used\r\n");
                                return 1;
                        } else {
                                LSV_DBUG("lba check not used\r\n");
                                return 0;
                        }
                }

                if (node->next) {
                        stack_push(&stack, node->next);
                }

                if (node->first_child) {
                        stack_push(&stack, node->first_child);
                }
        }

        LSV_DBUG("lba check not found snap..\r\n");
        // second time, means snapshot had been removed.
        stack_push(&stack, bitmap_context);

        while (!stack_empty(&stack)) {
                struct lsv_bitmap_context *node = stack_pop(&stack);
                struct lsv_bitmap_unit bitmap;

                if (node->bitmap_header->node_id > snap_id) {
                        int ret = lsv_bitmap_paged_read_node(node, lba, &bitmap);
                        if (ret)
                                return ret;

                        if (bitmap.chunk_id == chunk_id && bitmap.chunk_page_off == chunk_page_off)// data used.
                                return 1;
                } else// yeah, else.
                {
                        if (node->first_child) {
                                stack_push(&stack, node->first_child);
                        }
                }

                // needed to check brother.
                if (node->next) {
                        stack_push(&stack, node->next);
                }
        }

        return 0;

        /*
                if(bitmap_context->first_child)
                {
                        ret = lsv_bitmap_lba_check_node(bitmap_context->first_child, lba, chunk_id, chunk_page_off);
                        if(ret)
                                return ret;
                }

                if(bitmap_context->next)
                {
                        ret = lsv_bitmap_lba_check_node(bitmap_context->next, lba, chunk_id, chunk_page_off);
                        if(ret)
                                return ret;
                }

                if(bitmap.chunk_id == chunk_id && bitmap.chunk_page_off == chunk_page_off) //data used.
                        return 1;
                else
                        return 0;
         */
}

int lsv_bitmap_lba_check(void *volume_context, uint64_t lba, uint32_t chunk_id, uint32_t chunk_page_off, uint32_t snap_id)
{
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        int ret;

        lsv_bitmap_rlock(volume_context);
        ret = lsv_bitmap_lba_check_node(root, lba, chunk_id, chunk_page_off, snap_id);
        lsv_bitmap_unlock(volume_context);

        return ret;
}

int lsv_bitmap_lba_set_node(void *volume_context, struct lsv_bitmap_context *bitmap_context, lsv_bitmap_update_t *update_unit)
{
        stack_context_t stack;

        stack_init(&stack);

        stack_push(&stack, bitmap_context);

        while (!stack_empty(&stack)) {
                struct lsv_bitmap_context *node = stack_pop(&stack);
                struct lsv_bitmap_unit bitmap;

                int ret = lsv_bitmap_paged_read_node(node, update_unit->lba, &bitmap);
                if (ret)
                        return ret;

                LSV_DBUG("bitmap gc update, node_id=%ju, update_id=%d", node->bitmap_header->node_id, update_unit->snap_id);

                if (node->bitmap_header->node_id >= update_unit->snap_id && bitmap.chunk_id == update_unit->old_chunk_id &&
                    bitmap.chunk_page_off == update_unit->old_chunk_page_off)// data used.
                {
                        bitmap.chunk_id = update_unit->new_chunk_id;
                        bitmap.chunk_page_off = update_unit->new_chunk_page_off;
#if LSV_BITMAP_CHECK_BITMAP_LBA
                        bitmap.lba = update_unit->lba;
#endif
                        ret = lsv_bitmap_paged_write_node(volume_context, node, update_unit->lba, &bitmap, lsv_feature & LSV_FEATURE_BITMAP_GC_VALUE_UP);
                        if (!ret) {
                                LSV_DBUG("bitmap gc updated, old_chunk_id=%d, new_chunk_id=%d, old_off=%d, new_off=%d\r\n", update_unit->old_chunk_id,
                                         update_unit->new_chunk_id, update_unit->old_chunk_page_off, update_unit->new_chunk_page_off);

                                update_unit->repeat_count++;
                        } else
                                return ret;
                }

                if (node->next) {
                        stack_push(&stack, node->next);
                        // ret = lsv_bitmap_lba_set_node(bitmap_context->next, update_unit);
                        // if(ret)
                        //        return ret;
                }

                if (node->first_child) {
                        stack_push(&stack, node->first_child);
                        // ret = lsv_bitmap_lba_set_node(bitmap_context->first_child, update_unit);
                        // if(ret)
                        //       return ret;
                }
        }

        return 0;
}

int lsv_bitmap_lba_set(void *volume_context, lsv_bitmap_update_t *update_unit)
{
        int ret;
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        update_unit->repeat_count = 0;

        lsv_bitmap_rlock(volume_context);

        ret = lsv_bitmap_lba_set_node(volume_context, root, update_unit);

        lsv_bitmap_unlock(volume_context);

        if (ret)
                return ret;

        if (update_unit->repeat_count)
                return 0;
        else
                return 1;
}

int row_bitmap_page_get_extents(row2_bitmap_unit_t *bitmap, uint32_t page_idx, uint32_t *chunk_id, uint32_t *vvol_id, uint32_t *n_repeats);

int lsv_bitmap_full_clone_chunk(void *volume_context, uint8_t *bitmap_chunk_buf)
{
        int ret = 0;
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)volume_context)->bitmap_context;
        lsv_bitmap_header_t *pheader = root->bitmap_header;
        uint8_t *data = xmalloc(CHUNK_SIZE);
        row2_bitmap_unit_t *bitmap = (row2_bitmap_unit_t *)bitmap_chunk_buf;

        for (int i = 0; i < CHUNK_SIZE / sizeof(row2_bitmap_unit_t); i++) {
                uint32_t page_idx = 0;

                if (bitmap->chunk_id && !bitmap->owner) {
                        ret = lsv_volume_chunk_malloc((lsv_volume_proto_t *)volume_context,
                                                      LSV_LOG_LOG_STORAGE_TYPE,// lsv_u8_t type,
                                                      &bitmap->chunk_id);

                        if (ret) {
                                DFATAL("allocate chunk failed %d\r\n", ret);

                                goto end;
                        }

                        LSV_DBUG("allocated new data chunk, chunkd_id=%u\r\n", bitmap->chunk_id);

                        bitmap->owner = 1;
                }

                while (bitmap->chunk_id) {
                        uint32_t chunk_id;
                        uint32_t vvol_id;
                        uint32_t repeats;

                        row_bitmap_page_get_extents(bitmap, page_idx, &chunk_id, &vvol_id, &repeats);

                        if (chunk_id && vvol_id != pheader->vvol_id) {
                                uint64_t vol_id;

                                lsv_bitmap_vvol_to_vol(volume_context, vvol_id, &vol_id);

                                ret = volume_proto_remote_read_chunk(volume_context, vol_id, chunk_id, page_idx * LSV_PAGE_SIZE, repeats * LSV_PAGE_SIZE, data);
                                if (ret) {
                                        DFATAL("remote read chunk error %d\r\n", ret);

                                        goto end;
                                }

                                ret = lsv_bitmap_write_chunk(volume_context, bitmap->chunk_id, page_idx * LSV_PAGE_SIZE, repeats * LSV_PAGE_SIZE, data);
                                if (ret) {
                                        DFATAL("write chunk error %d\r\n", ret);

                                        goto end;
                                }

                                for (int j = page_idx; j < page_idx + repeats; j++) {
                                        bitmap->page_bits[j].chunk_id = bitmap->chunk_id;
                                        bitmap->page_bits[j].vvol_id = pheader->vvol_id;
                                }
                        }

                        page_idx += repeats;
                        if (page_idx >= sizeof(bitmap->page_bits) / sizeof(row2_bitmap_unit_t))
                                break;
                }

                bitmap++;
        }

end:

        xfree(data);

        return ret;
}

void row2_data_cow_callback(uint8_t *dataptr);
void lsv_bitmap_snap_full_clone_callback(void *arg)
{
        int ret = 0, i;
        struct lsv_bitmap_context *node = (struct lsv_bitmap_context *)arg;
        struct lsv_bitmap_context *root = ((lsv_volume_proto_t *)node->volume_context)->bitmap_context;
        lsv_bitmap_header_t *pheader = node->bitmap_header;

        lsv_bitmap_start_session(node->volume_context);

        for (i = pheader->reserved2[0]; i < root->bitmap_header->chunk_map_count; i++) {
                lsv_bitmap_cache_unit_t *ref, *new_ref;

                if (pheader->chunk_map[i].chunk_id == 0)// empty or owner
                        continue;

                // if(pheader->chunk_map[i].vvol_id == pheader->vvol_id)
                //        continue;

                uint8_t *cache_buf = lsv_bitmap_cache_get(node, pheader->chunk_map[i].vvol_id, pheader->chunk_map[i].chunk_id, 0, 0, 1, &ref);
                assert(cache_buf);
                assert(ref->chunk_id == pheader->chunk_map[i].chunk_id);

                uint8_t *new_cache_buf = cache_buf;
                if (pheader->chunk_map[i].is_ref) {
                        uint32_t new_chunk_id;
                        ret = lsv_bitmap_alloc_chunk(root->volume_context, &new_chunk_id, 0);// chunk is replaced, important, may yeild.
                        if (ret) {
                                lsv_bitmap_cache_unlock(ref);
                                goto end;
                        }

                        LSV_DBUG("allocated new bitmap chunk, chunkd_id=%u\r\n", new_chunk_id);

                        new_cache_buf = lsv_bitmap_cache_get(node, pheader->vvol_id, 0, 0, 0, 1, &new_ref);// on new vol.
                        assert(new_cache_buf);

                        new_ref->chunk_id = new_chunk_id;
                        memcpy(new_cache_buf, cache_buf, CHUNK_SIZE);

                        lsv_bitmap_cache_mark_dirty(new_ref, 0, BITMAP_CHUNK_SIZE / PAGE_SIZE);
                        row2_data_cow_callback(new_cache_buf);

                        pheader->chunk_map[i].is_ref = 0;
                        pheader->chunk_map[i].chunk_id = new_chunk_id;
                        pheader->chunk_map[i].vvol_id = root->bitmap_header->vvol_id;

                        lsv_bitmap_cache_unlock(new_ref);
                }

                ret = lsv_bitmap_full_clone_chunk(root->volume_context, new_cache_buf);

                lsv_bitmap_cache_unlock(ref);

                if (ret) {
                        DFATAL("clone chunk failed, chunk_id=%u, err=%d\r\n", pheader->chunk_map[i].chunk_id, ret);

                        goto end;
                }

                if (i - pheader->reserved2[0] > 8) {
                        break;
                }
        }

        pheader->reserved2[0] = i;

        if (pheader->reserved2[0] == root->bitmap_header->chunk_map_count) {
                LSV_DBUG("full cloned volume finished.\r\n");
                {
                        root->is_cloning = 0;

                        lsv_volume_proto_t *lsv_info = (lsv_volume_proto_t *)node->volume_context;

                        lsv_info->volume_proto->table1.fileinfo.source = 0;
                        lsv_info->volume_proto->table1.fileinfo.snap[0] = 0;
                        lsv_info->volume_proto->table1.table_proto->setinfo(lsv_info->volume_proto->table1.table_proto,
                                                                            &lsv_info->volume_proto->table1.fileinfo,
                                                                            sizeof(lsv_info->volume_proto->table1.fileinfo), TABLE_PROTO_INFO_ATTR);
                }
        }
end:
        lsv_bitmap_commit_dirty(root->volume_context);

        ret |= bitmap_header_save(root, SAVE_HEADER_LEVEL_ALL);

        if (ret) {
                DFATAL("full cloned failed, index=%u, err=%d\r\n", pheader->reserved2[0], ret);
        } else {
                LSV_DBUG("full cloned chunk, index=%d\r\n", pheader->reserved2[0]);

                if (pheader->reserved2[0] < pheader->chunk_map_count) {
                        schedule_task_new("lsv_bitmap_snap_full_clone", lsv_bitmap_snap_full_clone_callback, root, -1);
                }
        }

        return;
}

int lsv_bitmap_snap_full_clone(void *volume_context)
{
        lsv_volume_proto_t *volume = (lsv_volume_proto_t *)volume_context;
        struct lsv_bitmap_context *bitmap_root = (struct lsv_bitmap_context *)volume->bitmap_context;

        if (bitmap_root->is_cloning)
                return EEXIST;
        // if(!bitmap_root) //first one.
        //        bitmap_root = node;

        bitmap_root->bitmap_header->reserved2[0] = 0;

        schedule_task_new("lsv_bitmap_snap_full_clone", lsv_bitmap_snap_full_clone_callback, bitmap_root, -1);

        return 0;
}
